package com.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Interval{
	 int start;
	 int end;
	 Interval() { start = 0; end = 0; }
	 Interval(int s, int e) { start = s; end = e; }
}
public class MergeIntervals {

	public static String toString(List<Interval> intervals){
	   String s="[";
	   for(int i=0;i<intervals.size();i++){
		   s+="["+intervals.get(i).start+","+intervals.get(i).end+"]";
	   }
	   s+="]";
	   return s;
	}

	public static Interval[] toArray(List<Interval> list){
		int size=list.size();
		Interval[] itvs=new Interval[size];
		for(int i=0;i<size;i++){
			itvs[i]=list.get(i);
		}
		return itvs;
	}
	public static void main(String[] args) {
		List<Interval> intervals=new ArrayList<Interval>();
		System.out.println(MergeIntervals.toString(intervals));
		Interval[] itvs={
				
				new Interval(1,4),
				new Interval(0,5),
				new Interval(2,6),
				new Interval(1,3),
				new Interval(4,7),
				new Interval(3,5),
				new Interval(8,10),
				new Interval(12,13),
				new Interval(1,17),
				};
		for(Interval itv:itvs){
			intervals.add(itv);
		}
		List<Interval> resultIntervals=merge(intervals);
	    
		System.out.println(MergeIntervals.toString(resultIntervals));
	
	}
	
    public static List<Interval> merge(List<Interval> intervals) {
        if(intervals.isEmpty()) return intervals;
        Interval[] itvs=toArray(intervals);
        mergeSort(itvs, new Interval[intervals.size()], 0, intervals.size()-1);
      // sortList(intervals);
        intervals=Arrays.asList(itvs);
        intervals=new ArrayList<Interval>(intervals);
        int i=0;
        int len=intervals.size();
        for(i=0;i<len-1;){
        	if(intervals.get(i).end>=intervals.get(i+1).start){
        		int s=intervals.get(i).start;//<newIntervals.get(i+1).start?newIntervals.get(i).start:newIntervals.get(i+1).start;
        		int e=intervals.get(i).end>intervals.get(i+1).end?intervals.get(i).end:intervals.get(i+1).end;
        		Interval itv=new Interval(s, e);
        		intervals.remove(i);
        		intervals.add(i, itv);
        		intervals.remove(i+1);
        		
        		len--;	
        	}else{
        		i++;
        	}
        }
    	return intervals;
    }
    
    public static void sortList(List<Interval> intervals){
    	int len=intervals.size();
    	for(int i=0;i<len-1;i++){
    		for(int j=0;j<len-1-i;j++){
    			if(intervals.get(j).start>intervals.get(j+1).start){
    				int tempa=intervals.get(j).start;
    				int tempb=intervals.get(j).end;
    				intervals.get(j).start=intervals.get(j+1).start;
    				intervals.get(j).end=intervals.get(j+1).end;
    				intervals.get(j+1).start=tempa;
    				intervals.get(j+1).end=tempb;
    			}
    			
    		}
    	}
    }
    
    public static void mergeSort(Interval[] iDatas,Interval[] iBuffer, int iLow, int iHigh){
		if(iHigh>iLow){
			int iMid=(iHigh+iLow)/2;
			mergeSort(iDatas, iBuffer, iLow, iMid);
			mergeSort(iDatas, iBuffer, iMid+1, iHigh);
			merge(iDatas,iBuffer,iLow,iMid,iHigh);
			for(int i=iLow;i<=iHigh;i++){
				//iDatas.add(i,iBuffer.get(i));
				iDatas[i]=iBuffer[i];
			}
		}
	}
	
	public static void merge(Interval[] iDatas,Interval[] iBuffer,int iLow,int iMid,int iHigh){
		int i=iLow,j=iMid+1,k=iLow;
		while(i<=iMid&&j<=iHigh){
			if(iDatas[i].start<=iDatas[j].start){
				//iBuffer.add(k++, iDatas.get(i++));
				iBuffer[k++]=iDatas[i++];
			}else{
				//iBuffer.add(k++, iDatas.get(j++));
				iBuffer[k++]=iDatas[j++];
			}
		}
		if(i<=iMid){
			for(int ii=i;ii<=iMid;ii++)
				//iBuffer.add(k++, iDatas.get(ii));
				iBuffer[k++]=iDatas[ii];
		}else{
			for(int ii=j;ii<=iHigh;ii++)
				//iBuffer.add(k++, iDatas.get(ii));
				iBuffer[k++]=iDatas[ii];
		}
	}
}
